package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0139.java
 * @Author : WangRuoyu
 * @Date 2023/11/25 22:33
 */

public class Q0139 {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[][] f = new boolean[s.length() + 1][s.length() + 1];
        for (int len = 0; len <= s.length(); len++) {
            for (int i = 0, j = i + len; j <= s.length(); i++, j++) {
                if (i == j) {
                    f[i][j] = true;
                    continue;
                }
                for (String word : wordDict) {
                    if (word.length() <= j - i) {
                        String tmp = s.substring(i, j);
                        if (tmp.startsWith(word)) {
                            f[i][j] |= f[i + word.length()][j];
                        }
                        if (tmp.endsWith(word)) {
                            f[i][j] |= f[i][j - word.length()];
                        }
                        if (f[i][j]) break;
                    }
                }
            }
        }
        return f[0][s.length()];
    }

    public static void main(String[] args) {
        Q0139 sl = new Q0139();
        String s = "leetcode";
        List<String> wordDict = new ArrayList<String>(List.of(new String[]{"leet", "code"}));
        System.out.println(sl.wordBreak(s, wordDict));
    }
}